Quantum computers have far more computing power than classical computers. This is because of the properties called quantum parallel operation. Plenty of questions cannot be solved with a classical computer because it will cost ridiculous resources. Quantum computer can solve some of these problems because of quantum parallel operation. Based on this properties, a lot of quantum algorithms have been designed. Grover’s search algorithm^[1] and Shor’s factorization algorithm are included.^[2] Since quantum computers are based on quantum gates and all quantum gates are reversible, the research of reversible gates plays an important role in quantum computers.

The research of reversible gates is an important branch of basis mathematics. The reason why reversible gates were the first choice is that it does not consume any energy in theory. Based on Landauer’s principles,^[3] if a computation could be done reversibly, then the energy consumed can be zero. Since a reversible gate maps each input vector to an output vector uniquely and vice versa,^[4] that means a reversible computation does not erase any information, it does not cost any energy. Besides the application in quantum computer, reversible gates are also widely used in other fields, such as low power CMOS systems,^[5] optical computing,^[6] DNA computing,^[7] and nanotechnology.^[8] It is very clear that the research of reversible gates will provide a solid theoretical basis for fundamentals and applications.

Arithmetic adders and multipliers are the fundamental component in computational units. It is clear that adders and multipliers are the fundamental of a classical computer. As a result, quantum adders and multipliers should be designed to build perfect quantum computers. However, it lies a question: classical adders and multipliers are irreversible (most classical logic gates are irreversible such as AND and OR), hence they cannot be used directly in quantum computers. Thus, quantum arithmetic operations must be built from reversible gates.^[9] Based on this idea, lots of reversible adders and multipliers using different reversible gates have been proposed. A design of reversible full adders using two RG gates is introduced in Ref. [10]. Thersesal et al.^[11] have proposed a new reversible gate called NR gate, then used this gate to construct a full adder and a subtractor. Thapilyal et al.^[12] used TR gate to build a full adder, and it has been optimized. Islam et al.^[13] have proposed a full adder with two P gates, and the quantum cost has been optimized by Banerjee et al.^[14] A new reversible gate was introduced in Ref. [15], then it has been used to made a full adder and a subtractor.^[16]

In this paper, we focus on the quantum legitimacy of main reversible gates and a new design of multiplier using R gate. We are going to show the quantum legitimacy of N, C, T, P and R gates. Then we propose a new design of a full adder using R gate. We show that when we use the new full adder to build a multiplier, our new designed multiplier has absolute advantage than using the existed full adder based on R gate, and our design has the lowest garbage bit and quantum cost, then we explain the advantages of using R gate to build quantum Arithmetic operations. The chapters are distributed as follows: In Section 2, we introduce some definitions and facts which will be referred in this paper. Section 3 lists some reversible gates, and shows the quantum legitimacy of these reversible gates. In Section 4, we propose a new design of a full adder, then build a multiplier with it. In Section 5, we give conclusions and compare our designs with relevant designs proposed by others.

First, we recall some basic concepts and facts.

There are many reversible gates, and these gates can used to construct lots of circuits. In this section we introduce some common reversible gates and show the matrix of them, so that these reversible gates can be used as quantum gates, which means that circuits based on these gates are also suitable for quantum computers.

The NOT gate (N) is a one-bit gate, it flips the input bits unconditionally. The quantum cost of NOT gate is zero. it is trivial that for a 1 × 1 reversible circuit, there is only one NOT gate. In quantum computation, it is called the Pauli matrix, and it can be represented by matrix .

The controlled-NOT gate or CNOT gate is a reversible gate, and also a two-qubit quantum gate. The quantum cost of CNOT gate is one. It is easy to see that there are two possible CNOT gates for a 2×2 circuit. The action of the CNOT gate is given by |c〉|t〉→ |c〉|c⊕ t〉, that is, if the control qubit is set to |1〉, then the target qubit will be flipped, otherwise the target qubit will be let alone. Thus, the matrix representation of CNOT are

The Toffoli gate (T) is a 3 × 3 reversible gate, and also a three-qubit quantum gate. The quantum cost of Toffoli gate is five. There are three possible Toffoli gates for a 3 × 3 circuit. The circuit representation is shown in Fig. 1. The action of the Toffoli gate is given by |a〉|b〉|c〉→ |ab〉⊕ c〉, that is, if the control qubit |x〉 and |y〉 are set to |1〉 at the same time, then the target qubit will be flipped, otherwise the target qubit will be let alone. Thus, the matrix representation of Toffoli gates are

Fig. 1.

	Figure Option ViewDownloadNew Window
	Fig. 1. The Toffoli gate: (a) T(2,3,1), (b) T(1,3,2), and (c) T(1,2,3).

The Fredkin gate (F) is a 3 × 3 reversible gate, and also a three-qubit quantum gate. The quantum cost of Fredkin gate is five, which was optimized in Ref. [22]. There are three possible Fredkin gates for a 3 × 3 circuit. The circuit representation is shown in Fig. 2. The action of the Fredkin gate is that, if the control qubit |x〉 is set to |1〉, then swap the values of the other two qubits, otherwise the gate will do nothing. Thus, the matrix representations of Fredkin gates are

Fig. 2.

	Figure Option ViewDownloadNew Window
	Fig. 2. The Fredkin gate: (a) F(1,2,3), (b) F(3,1,2), and (c) F(2,1,3).

The Rⁿ gate is an n-qubit universal reversible gate, we can make a universal gate library only used Rⁿ gate. It was first introduced in Ref. [15] and used to construct a full adder/substractor in Ref. [16]. It combines the functionality of the NOT gate, the CNOT gate and the Toffoli gate. We will make a multiplier using R³ gate, so we introduce R¹, R² and R³ only.

The R¹ gate is just like NOT gate, it is a 1 × 1 gate, and flips the input qubit unconditionally. The quantum cost of R¹ gate is zero.

The R² gate is a combine of NOT gate and CNOT gate. If the control qubit is set to |1〉 then the target qubit is flipped, otherwise the target qubit is let alone, then flips the control qubit unconditionally. The quantum cost of R² gate is one. There are two possible R² gate for a 2 × 2 circuit. Figure 3 shows the circuit representation. It can be represented by

Fig. 3.

	Figure Option ViewDownloadNew Window
	Fig. 3. The R2 gate: (a) R(1,2) and (b) R(2,1).

The R³ gate is a three-qubit gate, the function of this gate can be described as follows: firstly use |x〉 and |y〉 as control bits to flip |z〉. Secondly |x〉 is used as a control bit to flip |y〉, then flips |z〉 unconditionally. Finally use |z〉 as control bit to flip |x〉. The quantum cost of R³ gate can be optimized to four with moving rules.^[23][24] There are six possible R³ gates for a 3 × 3 circuit. Figure 4 shows the circuit representation and figure 5 shows the optimization process. It is easy to calculate the matrix corresponding to each R³ gate, we list the calculation results in the following:

Fig. 4.

	Figure Option ViewDownloadNew Window
	Fig. 4. The R3 gate: (a) R(3,1,2), (b) R(1,3,2). We do not list all representations of R3 gate, the others are similar to these two examples.

Fig. 5.

	Figure Option ViewDownloadNew Window
	Fig. 5. The optimization process.

In this section, we propose three new designs, which are a half adder, a full adder and a multiplier, designed using R gate.

The half adder can be used to calculate the operation S = X + Y and to carry out bit C. The combination of R³(3,1,2) and R²(2,1) can do this. We use three input qubits, i.e.,|x〉, |y〉, which is the target value, and a constant qubit |0〉. We can obtain three output qubits, the first one is the summation bit S_i, the second one is a garbage bit, and the third one is the carry out bit C_i. The quantum cost of our half adder is four. Figure 6 shows the proposed half adder.

Fig. 6.

	Figure Option ViewDownloadNew Window
	Fig. 6. The half adder using R gate.

Using this half adder, we can make a full adder. Figure 7 shows the full adder. This design uses two half adders and one constant bit to produce two garbage bit, the quantum cost of this full adder is six. Figure 8 shows the optimized process.

Fig. 7.

	Figure Option ViewDownloadNew Window
	Fig. 7. The full adder using R gate.

Fig. 8.

	Figure Option ViewDownloadNew Window
	Fig. 8. The optimization process.

Now we can apply our half adder and full adder to build a multiplier. A multiplier consists of a partial product generator circuit (PPCG) and a reversible parallel adder (RPA), we use the partial product generator circuit proposed in Ref. [14], then give the structure of an array multiplier in Fig. 9.

Fig. 9.

	Figure Option ViewDownloadNew Window
	Fig. 9. RPA circuit.

It should be noted that the PPCG proposed in Ref. [14] uses only Toffoli gate, whereas we choose R gate library instead of NCT gate. This means that we need more R gate to synthesize a Toffoli gate in order to use this PPCG. However, it is worth. On the one hand, this circuit produces the lowest garbage bit, which is of great importance in a quantum computer. On the other hand, based on the view of Ref. [14] more quantum gates do not means more quantum cost. After simplification, we use the same numbers of N, V and U gates, which mean that in actual use, they do not make any difference, as a result, the gate number is out of consideration in this paper.

Finally, we compare our designs with the previous work in Tables 1 and 2. Table 1 shows the comparison of different full adders, and Table 2 shows the comparison of different multipliers. It is easy to see from Table 1 that our design has lower quantum cost than the existing design using R gate,^[16] and have the same garbage bit and quantum cost as the existing design,^[14] which means that it is the best design. From Table 2, we can see that our design is better than using the full adder proposed in Ref. [16] and has the lowest total cost.

Table 1.

Table 1.

Table 1. Comparison of the full adder. . Garbage bit Quantum cost Total cost Our proposed full adder 2 6 8 Full adder/substractor[16] 1 8 9 Existing full adder[13] 2 8 10 Existing full adder[14] 2 6 8

Table 1. Comparison of the full adder. .

Table 2.

Table 2.

Table 2. Comparison of full adder. . Garbage bit Quantum cost Total cost Our proposed multiplier 28 144 172 Existing multiplier[16] 28 160 188 Existing multiplier[14] 28 144 172 Existing multiplier[13] 52 140 192

Table 2. Comparison of full adder. .

We have shown the quantum legitimacy of some common reversible gate and given a new design of multiplier. It is very meaningful to show the quantum legitimacy of reversible gates. The difference between a reversible gate and a quantum gate is that a reversible use takes zero or one as the input while a quantum gate takes vector |0〉 and |1〉 as the input. However, giving a matrix representation to a reversible gate means that it can deal with a vector input, which means that many results based on reversible gates can be applied to quantum computer directly, and promote the research and development of related interdisciplinary subjects.

Our designs use local optimization rule in order to achieve the limit optimization of quantum cost and garbage bit, in this point it is similar to the existing design. However, compared with existed designs, our designs have lots of differences and advantages. The most obvious thing is that we use a new library. Our new designs are based on R gate library. R gate library is better than other gate libraries in many ways such as the size of minimal universal sub libraries, utilization of gate, the minimal length and so on. As a result, under the same condition, R gate library is a better choice than NCT gate libraries. However, as shown in Table 2, the multiplier using the previous adders is not optimal. Our designs make up for its defects in the multiplier part, and make the R gate library more advantageous in theoretical research and practical use. Moreover, our design pays more attention to the optimization of garbage bit, although it uses a little more gates, but it is worth. Regarding the comparison between our designs and the previous results, we have carried out a detailed analysis in Tables 1 and 2.